from typing import Tuple

class NestedInteger:
    def __init__(self, val):
        self.isInt = isinstance(val, int)
        if self.isInt:
            self.intVal = val
        else:
            self.listVal = val

    def isInteger(self) -> bool:
        """
        turn True if this NestedInteger holds a single integer, rather than a nested list.
        """
        return self.isInt

    def getInteger(self) -> int:
        """
        @return the single integer that this NestedInteger holds, if it holds a single integer
        Return None if this NestedInteger holds a nested list
        """
        return self.intVal

    def getList(self):
        """
        @return the nested list that this NestedInteger holds, if it holds a nested list
        Return None if this NestedInteger holds a single integer
        """
        return self.listVal


class NestedIterator:
    def __init__(self, nestedList):
        self.list = nestedList
        self.stack = [[nestedList, 0]]
        self.results = []

    def _next(self) -> Tuple[bool, int]:
        n_list, index = self.stack[-1]
        if index == len(n_list):
            self.stack.pop()
            if len(self.stack) == 0:
                return False, -1
            return self._next()
        self.stack[-1][1] += 1
        if n_list[index].isInteger():
            return True, n_list[index].getInteger()
        else:
            self.stack.append([n_list[index].getList(), 0])
            return self._next()

    def next(self):
        if len(self.results) != 0:
            n = self.results.pop()
        else:
            _, n = self._next()
        return n


    def hasNext(self) -> bool:
        has_next, n = self._next()
        self.results.insert(0, n)
        return has_next


if __name__ == '__main__':
    nestedList = [NestedInteger([NestedInteger(1), NestedInteger(1)]), NestedInteger(2), NestedInteger([NestedInteger(1), NestedInteger(1)])]
    i, v = NestedIterator(nestedList), []
    while i.hasNext(): v.append(i.next())
    print(v)
    nestedList = [NestedInteger([NestedInteger(1), NestedInteger([NestedInteger(4), NestedInteger([NestedInteger(6)])])])]
    i, v = NestedIterator(nestedList), []
    while i.hasNext(): v.append(i.next())
    print(v)
    nestedList = [NestedInteger([])]
    i, v = NestedIterator(nestedList), []
    while i.hasNext(): v.append(i.next())
    print(v)
